//
// Created by LONG on 2020/10/18.
//

#include <stddef.h>
#include <string.h>
#include "../../include/utils/listSort.h"

#define MAX_LIST_LENGTH_BITS 20

/*
 * Returns a list organized in an intermediate format suited
 * to chaining of merge() calls: null-terminated, no reserved or
 * sentinel head node, "prev" links not maintained.
 */
static S_List *__list_merge(list_cmp cmp, S_List *a, S_List *b)
{
    S_List head, *tail = &head;

    while (a && b)
    {
        /* if equal, take 'a' -- important for sort stability */
        if ((cmp)(a, b) <= 0)
        {
            tail->next = a;
            a = a->next;
        }
        else
        {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a ? : b;
    return head.next;
}

/*
 * Combine final list merge with restoration of standard doubly-linked
 * list structure.  This approach duplicates code from merge(), but
 * runs faster than the tidier alternatives of either a separate final
 * prev-link restoration pass, or maintaining the prev links
 * throughout.
 */
static void __list_merge_and_restore(list_cmp cmp, S_List *list, S_List *a,
    S_List *b)
{
    S_List *tail = list;

    while (a && b)
    {
        /* if equal, take 'a' -- important for sort stability */
        if ((cmp)(a, b) <= 0)
        {
            tail->next = a;
            a->prev = tail;
            a = a->next;
        }
        else
        {
            tail->next = b;
            b->prev = tail;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a ? : b;

    do
    {
        tail->next->prev = tail;
        tail = tail->next;
    } while (tail->next);

    tail->next = list;
    list->prev = tail;
}

void LIST_Sort(S_List *list, list_cmp cmp)
{
    S_List *part[MAX_LIST_LENGTH_BITS + 1];
    int lev;
    int max_lev = 0;
    S_List *list_tmp;

    if (LIST_Empty(list))
    {
        return;
    }

    memset(part, 0, sizeof(part));

    list->prev->next = NULL;
    list_tmp = list->next;

    while (list_tmp)
    {
        S_List *cur = list_tmp;
        list_tmp = list_tmp->next;
        cur->next = NULL;

        for (lev = 0; part[lev]; lev++)
        {
            cur = __list_merge(cmp, part[lev], cur);
            part[lev] = NULL;
        }
        if (lev > max_lev)
        {
            if (unlikely(lev >= ARRAY_SIZE(part)-1))
            {
                lev--;
            }
            max_lev = lev;
        }
        part[lev] = cur;
    }

    for (lev = 0; lev < max_lev; lev++)
    {
        if (part[lev])
        {
            list_tmp = __list_merge(cmp, part[lev], list_tmp);
        }
    }

    __list_merge_and_restore(cmp, list, part[max_lev], list_tmp);
}
